package leetcode.editor.cn.q1_300.q;

/**
 * @author qidi
 * @date 2021-11-22 16:17:30
 */
class Q0044_WildcardMatching {

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        public boolean isMatch(String s, String p) {
            int sRight = s.length(), pRight = p.length();
            while (sRight > 0 && pRight > 0 && p.charAt(pRight - 1) != '*') {
                if (charMatch(s.charAt(sRight - 1), p.charAt(pRight - 1))) {
                    --sRight;
                    --pRight;
                } else {
                    return false;
                }
            }

            if (pRight == 0) {
                return sRight == 0;
            }

            int sIndex = 0, pIndex = 0;
            int sRecord = -1, pRecord = -1;

            while (sIndex < sRight && pIndex < pRight) {
                if (p.charAt(pIndex) == '*') {
                    ++pIndex;
                    sRecord = sIndex;
                    pRecord = pIndex;
                } else if (charMatch(s.charAt(sIndex), p.charAt(pIndex))) {
                    ++sIndex;
                    ++pIndex;
                } else if (sRecord != -1 && sRecord + 1 < sRight) {
                    ++sRecord;
                    sIndex = sRecord;
                    pIndex = pRecord;
                } else {
                    return false;
                }
            }

            return allStars(p, pIndex, pRight);
        }

        public boolean allStars(String str, int left, int right) {
            for (int i = left; i < right; ++i) {
                if (str.charAt(i) != '*') {
                    return false;
                }
            }
            return true;
        }

        public boolean charMatch(char u, char v) {
            return u == v || v == '?';
        }
    }
    //leetcode submit region end(Prohibit modification and deletion)


    public static void main(String[] args) {
        Solution solution = new Q0044_WildcardMatching().new Solution();
//        System.out.println(solution.isMatch("aaab", "a*b*"));
        System.out.println(solution.isMatch("abb", "*??"));
//        System.out.println(solution.isMatch("hi", "*?"));
//        System.out.println(solution.isMatch("b", "*?*"));
//        System.out.println(solution.isMatch("mississippi", "m??*ss*?i*pi"));
//        System.out.println(solution.isMatch("abcabczzzde", "*abc???de*"));
//        System.out.println(solution.isMatch("", "******"));
//        System.out.println(solution.isMatch("aa", "a"));
//        System.out.println(solution.isMatch("cb", "?a"));
//        System.out.println(solution.isMatch("adceb", "a*b"));
//        System.out.println(solution.isMatch("acdcb", "a*c?b"));
//        System.out.println(solution.isMatch("adceb", "a**?b"));
    }
}